Climbing depth-bounded adjacent discrepancy search for solving hybrid flow shop scheduling problems with multiprocessor tasks

摘要

This paper considers multiprocessor task scheduling in a multistage hybridflow-shop environment. The problem even in its simplest form is NP-hard in thestrong sense. The great deal of interest for this problem, besides itstheoretical complexity, is animated by needs of various manufacturing andcomputing systems. We propose a new approach based on limited discrepancysearch to solve the problem. Our method is tested with reference to a proposedlower bound as well as the best-known solutions in literature. Computationalresults show that the developed approach is efficient in particular forlarge-size problems.